/*
 * Очередь с приоритетами
 */

#include <stdio.h>
#include <stdbool.h>
#include <stdint.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
#include <assert.h>

#ifdef DEBUG
# define debug_fprintf(x)	fprintf x
#else
# define debug_fprintf(x)	((void) 0)
#endif

#define S_assert(st) ((st)?((void)0):(void)fprintf(stderr,"Assertion (soft) \"%s\" in %s:%s():%d: failed.\n",#st,__FILE__,__func__,__LINE__))
#define SWAP_INT(a, b)	(((a) ^ (b)) && ((b) ^= (a) ^= (b), (a) ^= (b)))

/* queue */
struct queue {
	char *data;
	size_t _data_size;

	int head;
	int n;
	int _max;
};

/* stack */
struct stack {
	char *data;
	size_t n; /* how many elements in the stack atm */
	size_t _data_size; /* size of one element (in bytes) */
	size_t _allocated; /* how much storage is allocated for *data (in bytes) */
	size_t _max; /* maximum storage that we are allowed allocate for *data */
};

/* autoarray */
struct vector {
	char *data;
	size_t _elem_size;

	int n;
	int _max;
};

/* doubly-linked list */
struct dll_node {
	int x, y;
	char *data;
	size_t _data_size;
	struct dll_node *prev, *next;
};

/* priority queue */
struct pqueue {
	char *data; /* threres a reason why i use a continuous array */
	size_t _data_size;

	int n; /* amount of elements in the queue */
	int _max; /* maximum space allocated for .data */
	int (*cmp)(const void *, const void *); /* comaparator function */

	bool _autoexpand; /* trigger autoexpansion on new element insertion */
};

/* graph repr: adjlist w/ doubly-linked list */
enum vertex_st {
	VTX_ST_UNKN = 0,
	VTX_ST_ENQUEUED,
	VTX_ST_OPEN,
	VTX_ST_VISITED
};

struct adjlist_dll {
	struct dll_node *head;
	struct dll_node *tail;
	size_t _list_len;

	enum vertex_st state;
	int color;
	int distance;
	int parent;
	int fwd, bck; /* dfs tree depth, >=1 unless uninitialized */
	int low; /* lowpoint(), >=1 unless uninitialized */
	int chnum; /* children count for this node */
};

struct tuple {
	int key;
	int val;
};

struct reg {
	int *in_heap;
	int *in_vec;
	bool *extracted;
	int n;
};

/* {{{ function prototypes */
/* memory allocation wrappers */
void *s_calloc(size_t n, size_t size);
void *s_malloc(size_t size);
void *s_realloc(void *oldptr, size_t newsize);

char *bytes_to_str(const void *ptr, const size_t size);
/* }}} */

/* {{{ memory allocation wrappers */
extern void *s_calloc(size_t n, size_t size)
{
	void *ptr;
	ptr = calloc(n, size);
	assert(ptr != NULL);
	if (ptr == NULL) {
		fprintf(stderr, "%s(): out of memory, failed to allocate %lu bytes\n",
				__func__, n * size);
		abort();
	}
	return ptr;
}

extern void *s_malloc(size_t size)
{
	void *ptr;
	ptr = malloc(size);
	assert(ptr != NULL);
	if (ptr == NULL) {
		fprintf(stderr, "%s(): out of memory, failed to allocate %lu bytes\n",
				__func__, size);
		abort();
	}
	return ptr;
}

extern void *s_realloc(void *oldptr, size_t newsize)
{
	void *newptr;
	newptr = realloc(oldptr, newsize);
	if (newptr == NULL) {
		fprintf(stderr, "%s(): out of memory, "
				"failed to realloc %p for new size of %lu bytes\n",
				__func__, oldptr, newsize);
		abort();
	}
	return newptr;
}
/* }}} */

/* {{{ mergesort (with copy array optimization) */
static void
mergesort__merge(void *p1, size_t nmemb, size_t size,
		int (*cmpf)(const void *, const void *),
		void *p2, const int depth,
		size_t L, size_t M, size_t R)
{
	register char *base, *cpybuf;
	size_t i = L, j = M + 1;
	register size_t s = 0; /* points to where we will place next element */

	if (depth & 1)
		base = p1, cpybuf = p2;
	else
		base = p2, cpybuf = p1;

	while (i <= M && j <= R) {
		if (cmpf(base + i * size, base + j * size) <= 0) {
			if (i <= M) {
				memcpy(cpybuf + s*size, base + i*size, size);
				s++;
				i++;
			} else if (j <= R) {
				memcpy(cpybuf + s*size, base + j*size, size);
				s++;
				j++;
			}
		} else {
			if (j <= R) {
				memcpy(cpybuf + s*size, base + j*size, size);
				s++;
				j++;
			} else if (i <= M) {
				memcpy(cpybuf + s*size, base + i*size, size);
				s++;
				i++;
			}
		}
	}

	/*
	 * let's see how this works
	 */
	while (i <= M)
		memcpy(cpybuf + (s++) * size, base + (i++) * size, size);
	while (j <= R)
		memcpy(cpybuf + (s++) * size, base + (j++) * size, size);
}

static void
mergesort__main(void *base, size_t nmemb, size_t size,
		int (*cmpf)(const void *, const void *),
		void *cpybuf, const int depth,
		size_t L, size_t R)
{
	size_t M = (L + R) / 2;

	if (L < R) {
		mergesort__main(base, nmemb, size, cmpf, cpybuf, depth + 1, L, M);
		mergesort__main(base, nmemb, size, cmpf, cpybuf, depth + 1, M + 1, R);
		mergesort__merge(base, nmemb, size, cmpf, cpybuf, depth, L, M, R);
	}
}

extern void
mergesort(void *base, size_t nmemb, size_t size,
		int (*cmpf)(const void *, const void *))
{
	void *cpybuf;

	cpybuf = s_malloc(nmemb * size);
	memcpy(cpybuf, base, nmemb * size);
	mergesort__main(base, nmemb, size, cmpf, cpybuf, 0,
			0UL, nmemb - 1UL);
	free(cpybuf);
}
/* }}} */

/* {{{ priority queue */
/* {{{ heap mng */
static int
pqueue__heap_sift_down(struct pqueue *pq, int idx, struct reg *r)
{
	register int swap;
	int parent = idx, child;

	while (parent * 2 + 1 < pq->n) {
		child = parent * 2 + 1;
		swap = parent;

		if ((*pq->cmp)(pq->data + (parent) * pq->_data_size,
		               pq->data + (child) * pq->_data_size) > 0) {
			swap = child;
		}

		if (child + 1 < pq->n &&
		    (*pq->cmp)(pq->data + (swap) * pq->_data_size,
		               pq->data + (child + 1) * pq->_data_size) > 0) {
			swap = child + 1;
		}

		if (swap != parent) {
#ifdef DEBUG
			char *_bytes = bytes_to_str(pq->data + (parent) * pq->_data_size,
										pq->_data_size);
			fprintf(stderr, "%s(): swapping (%s) with ", __func__, _bytes);
			free(_bytes);
			_bytes = bytes_to_str(pq->data + (swap) * pq->_data_size,
							pq->_data_size);
			fprintf(stderr, "(%s)\n", _bytes);
			free(_bytes);
#endif
			memmove(pq->data + (pq->n) * pq->_data_size,
					pq->data + (parent) * pq->_data_size,
					pq->_data_size);
			memmove(pq->data + (parent) * pq->_data_size,
					pq->data + (swap) * pq->_data_size,
					pq->_data_size);
			memmove(pq->data + (swap) * pq->_data_size,
					pq->data + (pq->n) * pq->_data_size,
					pq->_data_size);
			SWAP_INT(r->in_heap[r->in_vec[parent]], r->in_heap[r->in_vec[swap]]);
			SWAP_INT(r->in_vec[parent], r->in_vec[swap]);
			parent = swap;
		} else {
			return 1;
		}
	}

	return 2;
}

static int
pqueue__heap_sift_up(struct pqueue *pq, int idx, struct reg *r)
{
	int child = idx, parent = (idx - 1) / 2;

	while (child > 0) {
		if ((*pq->cmp)(pq->data + (parent) * pq->_data_size,
						pq->data + (child) * pq->_data_size) > 0) {
#ifdef DEBUG
			char *_bytes = bytes_to_str(pq->data + (parent) * pq->_data_size,
										pq->_data_size);
			fprintf(stderr, "%s(): swapping (%s) with ", __func__, _bytes);
			free(_bytes);
			_bytes = bytes_to_str(pq->data + (child) * pq->_data_size,
							pq->_data_size);
			fprintf(stderr, "(%s)\n", _bytes);
			free(_bytes);
#endif
			memmove(pq->data + (pq->n) * pq->_data_size,
					pq->data + (parent) * pq->_data_size,
					pq->_data_size);
			memmove(pq->data + (parent) * pq->_data_size,
					pq->data + (child) * pq->_data_size,
					pq->_data_size);
			memmove(pq->data + (child) * pq->_data_size,
					pq->data + (pq->n) * pq->_data_size,
					pq->_data_size);
			SWAP_INT(r->in_heap[r->in_vec[parent]], r->in_heap[r->in_vec[child]]);
			SWAP_INT(r->in_vec[parent], r->in_vec[child]);

			child = parent--;
			parent /= 2;
		} else {
			return 1;
		}
	}

	return 2;
}
/* }}} */
/*
 * Returns an initialized pqueue
 */
extern struct pqueue *
pqueue__new(const size_t elem_size, int exp, const bool autoexpand,
		int (*f)(const void *, const void *))
{
	struct pqueue *pq;

	/* if (f == NULL) f = &numcmp; default to integers */
	if (exp <= 0) exp = 6; /* default to 64 elements */
	S_assert(exp <= 23); /* 8,388,608 elements _might_ be a little too much */
	assert(elem_size != 0);

	pq = s_malloc(sizeof *pq);
	pq->data = s_calloc((pq->_max = 1<<exp), (pq->_data_size = elem_size));
	pq->n = 0;
	pq->cmp = f;
	pq->_autoexpand = autoexpand; /* TODO */

	return pq;
}

/*
 * Insert element that 'elem' points to into the pqueue.
 */
extern int
pqueue__insert(struct pqueue *pq, const struct tuple *elem, struct reg *r)
{
	char *tmp = NULL;

	if (pq == NULL) {
		fprintf(stderr, "%s(): pq == NULL, not doing anything (-2)\n", __func__);
		return -2;
	}

	if (elem == NULL) {
		fprintf(stderr, "%s(): elem == NULL, what am i supposed to insert? (-1)\n", __func__);
		return -1;
	}

	if (pq->n + 1 >= pq->_max) {
		/* i betcha the ">=" makes you wonder .. */
		tmp = s_realloc(pq->data, (pq->_max <<= 1) * pq->_data_size);
		assert(tmp != NULL);
		pq->data = tmp;
	}
	memcpy(pq->data + (pq->_data_size * pq->n), elem, pq->_data_size);
	r->in_heap[elem->key] = pq->n;
	r->in_vec[pq->n] = elem->key;

	pqueue__heap_sift_up(pq, pq->n++, r);

	return 0;
}

/*
 * Extract the top element from the pqueue and put it into 'obuf' buffer.
 */
extern int
pqueue__extract(struct pqueue *pq, void *buf, struct reg *r)
{
	if (pq == NULL) {
		fprintf(stderr, "%s(): received a NULL ptr, not doing anything (-1)\n", __func__);
		return -1;
	}

	if (buf != NULL)
		memcpy(buf, pq->data, pq->_data_size);
	memmove(pq->data, pq->data + (--pq->n) * pq->_data_size, pq->_data_size);
	r->extracted[r->in_vec[0]] = true;
	r->in_heap[r->in_vec[0]] = -1;
	r->in_heap[r->in_vec[pq->n]] = 0;
	SWAP_INT(r->in_vec[0], r->in_vec[pq->n]);
	pqueue__heap_sift_down(pq, 0, r);

	return 0;
}

extern int
pqueue__cleanup(struct pqueue *pq)
{
	if (pq == NULL) {
		fprintf(stderr, "%s(): received a NULL ptr, not doing anything (-1)\n", __func__);
		return -1;
	}

	if (pq->_max > 0) {
		free(pq->data);
		pq->data = NULL;
	}
	free(pq);

	return 0;
}
/* }}} */

/* {{{ misc */
extern char *
bytes_to_str(const void *ptr, const size_t size)
{
	char *str;
	const unsigned char *byte = ptr;
	int offset;

	/* each byte is represented as "0x??" and a
	 * whitespace character in between */
	str = s_malloc(5 * size + 1);
	for (offset = 0; offset < size; offset++) {
		sprintf(str + offset * 5, "0x%02hhx ", byte[offset]);
	}
	str[size * 5 - 1] = '\0';

	return str;
}
/* }}} */

int
cmp(const void *p1, const void *p2)
{
	const struct tuple *t1 = p1, *t2 = p2;

	assert(p1 && p2);
	if (t1->val > t2->val)
		return 1;
	if (t1->val == t2->val)
		return 0;
	return -1;
}

int
main(void)
{
	struct pqueue *pq;
	struct reg r;
	struct tuple T, *pqdata;
	int n, cmd_n, key, val, cmd;
	register int i;

	scanf("%d %d", &n, &cmd_n);
	pq = pqueue__new(sizeof T, 17, false, &cmp);
	r.in_heap = s_calloc(n, sizeof r.in_heap[0]);
	r.in_vec = s_calloc(n, sizeof r.in_vec[0]);
	r.extracted = s_calloc(n, sizeof r.extracted[0]);
	r.n = n;

	T.val = INT_MAX;
	for (i = 0; i < n; i++) {
		T.key = i;
		pqueue__insert(pq, &T, &r);
	}
	pqdata = pq->data;

	for (i = 0; i < cmd_n; i++) {
		scanf("%d", &cmd);

		if (cmd == 0) {
			scanf("%d %d", &key, &val);
			key--;

			if (r.extracted[key])
				continue;

			if (pqdata[r.in_heap[key]].val > val) {
				pqdata[r.in_heap[key]].val = val;
				pqueue__heap_sift_up(pq, r.in_heap[key], &r);
			} else {
				pqdata[r.in_heap[key]].val = val;
				pqueue__heap_sift_down(pq, r.in_heap[key], &r);
			}
		} else if (cmd == 1) {
			pqueue__extract(pq, &T, &r);
			printf("%d %d\n", T.key + 1, T.val);
		}
	}

	pqueue__cleanup(pq);
	free(r.in_heap);
	free(r.extracted);
	free(r.in_vec);
	return 0;
}
